/*
* Copyright (c) 2006-2009 Erin Catto http://www.gphysics.com
*
* This software is provided 'as-is', without any express or implied
* warranty.  In no event will the authors be held liable for any damages
* arising from the use of this software.
* Permission is granted to anyone to use this software for any purpose,
* including commercial applications, and to alter it and redistribute it
* freely, subject to the following restrictions:
* 1. The origin of this software must not be misrepresented; you must not
* claim that you wrote the original software. If you use this software
* in a product, an acknowledgment in the product documentation would be
* appreciated but is not required.
* 2. Altered source versions must be plainly marked as such, and must not be
* misrepresented as being the original software.
* 3. This notice may not be removed or altered from any source distribution.
*/

#ifndef B2_COLLISION_H
#define B2_COLLISION_H

#include "../Common/b2Math.h"
#include <climits>

/// @file
/// Structures and functions used for computing contact points, distance queries and TOI queries.

class b2Shape;
class b2CircleShape;
class b2PolygonShape;
class b2EdgeShape;

const uint8 b2_nullFeature = UCHAR_MAX;

/// Contact ids to facilitate warm starting.
union b2ContactID
{
	/// The features that intersect to form the contact point.
	struct Features
	{
		uint8 referenceEdge;	/// The edge that defines the outward contact normal.
		uint8 incidentEdge;		/// The edge most anti-parallel  to the reference edge.
		uint8 incedentVertex;	/// The vertex (0 or 1) on the incident edge that was clipped.
		uint8 flip;				/// A Value of 1 indicates that the reference edge is on Shap2.
	}features;
	uint32  key;				/// used to quickly compare contact ids.
};

/// A manifold point is a contact point than belongs to a contact manifold.
/// It hold the details related to the geometry and dynamics of the contact points.
/// The local point usage depends on the manifold type:
/// -e_circles: the local center of circle B.
/// -e_faceA: the local center of circle B or the clip point of polygon B.
/// -e_faceB: the clip point of polygon A.
/// This struct is stored across time step, so we keep it small.
/// Note: the impulses are used for internal caching and may not provide reliable contact forces, 
/// especially for high speed collisions.
struct b2ManifoldPoint
{
	b2Vec2 m_localPoint;	/// usage depend on manifold type.
	float32 m_normalImpulse;	/// the none-penetration impulse.
	float32 m_tangentImpulse;	/// the friction impulse.
	b2ContactID m_id;			/// uniquely identifies a contact point between two shapes.
};

/// A manifold for two touching convex shapes.
/// Box2D support multiple types of contact point:
/// - clip point versus plane with radius.
/// - point versus point with radius(circles).
/// The local point usage depend on the manifold type:
/// -e_circles: the local center of circle A.
/// -e_faceA: the center of face A.
/// -e_faceB: the center of face B.
/// Similarly the local normal usage.
/// -e_circla: not used.
/// -e_faceA: the normal on polygon A.
/// -e_faceB: the normal on polygon B.
/// We store contacts in this way so that position correction can account for movement. which is critical for continous collision.
/// All contact scenarios must be expressed in one of these types.
/// This struct is stored across time steps. so,we keep it small.
struct b2Manifold
{
	enum Type
	{
		e_circles,
		e_faceA,
		e_faceB,
	};

	b2ManifoldPoint m_points[b2_maxManifoldPoints];		/// the point of contacts.
	b2Vec2	m_localPlaneNormal;							/// not used for type e_point
	b2Vec2	m_localPoint;								/// usage depend on manifold type.
	Type	m_type;
	int32	m_pointCount;								/// the number of manifold point.
};

/// This is used for computing the current status of a contact manifold.
struct b2WorldManifold
{
	/// Evaluate the manifold with supplied transforms, this assumes modest motion from the original state.
	/// This does not change the point count, impulses, etc. the radii must come from the shapes that generate
	/// the manifold.
	void Initialize(const b2Manifold* manifold, const b2XForm& xfA, float32 radiusA, const b2XForm& xfB, float32 radiusB);

	b2Vec2 m_normal;		/// world vector pointing from A to B.
	b2Vec2 m_points[b2_maxManifoldPoints];		/// world contact points.
};

/// This is used for determining the state of the contact point.
enum b2PointState
{
	b2_nullState,	/// point does not exist.
	b2_addState,	/// point was add to the update.
	b2_persistState,	/// point persisted across the update.
	b2_removeState,		/// point was removed from the update.
};

/// Compute the point state given two manifold. the state pertains to the transformation from manifold1 to 
/// manifold2.so state1 is either persist or remove while state2 is either add or persisit.
void b2GetPointStates(b2PointState state1[b2_maxManifoldPoints], b2PointState state2[b2_maxManifoldPoints], const b2Manifold* manifold1, const b2Manifold* manifold2);

/// used for computing contact manifolds.
struct b2ClipVertex
{
	b2Vec2 v;
	b2ContactID id;
};

/// Ray-cast input data.
struct b2RayCastInput
{
	b2Vec2 p1, p2;
	float32 maxFriction;
};

/// Ray-cast output data.
struct b2RayCastOutput
{
	b2Vec2 normal;
	float32 friction;
	bool hit;
};


/// A line segment.
struct b2Segment
{
	/// Ray cast against this segment with another segment.
	bool  TestSegment(float32* lambda, b2Vec2* normal, const b2Segment& segment, float32 maxLambda) const;

	b2Vec2 p1, p2;	// the starting and ending point.
};

/// An axis aligned bounding box.
struct b2AABB
{
	/// Verify that the bounds are sorted.
	bool IsValid() const;

	/// Get the center of the AABB.
	b2Vec2 GetCenter() const
	{
		return 0.5f * (lowerBound + upperBound);
	}

	/// Get the extents of the AABB(half-widths).
	b2Vec2 GetExtents() const
	{
		return 0.5f * (lowerBound - upperBound);
	}

	/// Combine two AABBs into this one.
	void Combine(const b2AABB& aabb1, const b2AABB& aabb2)
	{
		lowerBound = b2Min(aabb1.lowerBound, aabb2.lowerBound);
		upperBound = b2Min(aabb1.upperBound, aabb2.upperBound);
	}

	/// Does this AABB contains the provided AABB.
	bool Contains(const b2AABB& aabb)
	{
		bool result = true;
		result = result && (lowerBound.x <= aabb.lowerBound.x);
		result = result && (lowerBound.y <= aabb.lowerBound.y);
		result = result && (aabb.upperBound.x <= upperBound.x);
		result = result && (aabb.upperBound.y <= upperBound.y);
		return result;
	}

	void RayCast(b2RayCastOutput* output, const b2RayCastInput& input);

	b2Vec2 lowerBound;	/// the lower vertex.
	b2Vec2 upperBound;	/// the upper vertex.
};

/// Compute the collision manifold between two circle.
void b2CollideCircles(b2Manifold* manifold, const b2CircleShape* circle1, const b2XForm& xf1, const b2CircleShape* circle2, const b2XForm& xf2);

/// Compute the collision manifold between a polygon and circle.
void b2CollidePolygonAndCircle(b2Manifold* manifold, const b2PolygonShape* polygon, const b2XForm& xf1, const b2CircleShape* circle, const b2XForm& xf2);
/// Compute the collision manifold between two polygons.
void b2CollidePolygons(b2Manifold* manifold, const b2PolygonShape* polygon1, const b2XForm& xf1, const b2PolygonShape* polygon2, const b2XForm& xf2);

/// Compute the collision manifold between an edge and Circle.
void b2CollideEdgeAndCircle(b2Manifold* manifold, const b2EdgeShape* edge, const b2XForm& xf1, const b2CircleShape* circle, const b2XForm& xf2);

/// Compute the collision manifold between an polygon and edge.
void b2CollidePolyAndEdge(b2Manifold* manifold, const b2PolygonShape* polygon, const b2XForm& xf1, const b2EdgeShape* edge, const b2XForm& xf2 );

/// Clipping for contact manifold.
int32 b2ClipSegmentToLine(b2ClipVertex vOut[2], const b2ClipVertex vIn[2], const b2Vec2& normal, float32 offset);

// ----------------Inline Functions------------------------------------------

inline bool b2AABB::IsValid() const
{
	b2Vec2 d = upperBound - lowerBound;
	bool valid = (d.x >= 0.0f) && (d.y >= 0.0f);
	valid = valid && lowerBound.IsValid() && upperBound.IsValid();
	return valid;
}

inline bool b2TestOverlap(const b2AABB& a, const b2AABB& b)
{
	b2Vec2 d1, d2;

	d1 = b.lowerBound - a.upperBound;
	d2 = a.lowerBound - a.upperBound;

	if(d1.x>0.0f || d1.y>0.0f || d2.x>0.0f || d2.y>0.0f)
	{
		return false;
	}

	return true;
}

#endif
